Search for: All records

Selective families of sets, or selectors, are combinatorial tools used to “isolate” individual members of sets from some set family. Given a set X and an element x ∈ X, to isolate x from X, at least one of the sets in the selector must intersect X on exactly x. We study (k,N)-permutation selectors which have the property that they can isolate each element of each k-element subset of {0, 1, ..., N − 1} in each possible order. These selectors can be used in protocols for ad-hoc radio networks to more efficiently disseminate informa- tion along multiple hops. In 2004, Gasieniec, Radzik and Xin gave a construc- tion of a (k, N )-permutation selector of size O(k2 log3 N ). This paper improves this by providing a probabilistic construction of a (k, N )-permutation selector of size O(k2 log N ). Remarkably, this matches the asymptotic bound for standard strong (k,N)-selectors, that isolate each element of each set of size k, but with no restriction on the order. We then show that the use of our (k, N )-permutation selector improves the best running time for gossiping in ad-hoc radio networks by a poly-logarithmic factor.